#include<iostream>
// zdl:: 这道题目如果想要直接使用贪心，是很容易直接举出返利的，现在就是使用正解，区间dp


using namespace std;
int n;
const int N = 2e3 + 10;
int f[N][N];
int v[N];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> v[i];
    // zdl:: 这些题目乍一看很难其实需要我们多思考哈
    for (int len = 1; len <= n; len++)
    {
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int j = i + len - 1;
            int m = n - len + 1;
            f[i][j] = max(f[i][j - 1] + v[j] * m, f[i + 1][j] + v[i] * m);
        }
    }


    cout << f[1][n] << endl;
    return 0; 
}


// zddl:: Yex!!!